//
// Created by Incredible on 17/3/21.
//

#ifndef UNIONFIND2_UNIONFIND2_H
#define UNIONFIND2_UNIONFIND2_H

#include <cassert>

namespace UF2 {
    using namespace std;

    class UnionFind {

    public:
        int *parent; //节点的父节点，
        int count; //数组大小

    public:

        //初始化并查集
        UnionFind(int count) {
            this->count = count;
            parent = new int[count];

            //将每个节点的根设置为自己，标识其没有根节点，自己就是根
            for (int i = 0; i < count; ++i) {
                parent[i] = i;
            }
        }

        //析构函数
        ~UnionFind() {
            delete[] parent;
        }

        //查找x的根节点
        int find(int x) {
            //断言 x 是否越界
            assert(x >= 0 && x < count);

            while (x != parent[x]) {
                x = parent[x];
            }
            return x;
        }

        //判断两个节点是否有关联
        bool isConnection(int x, int y) {
            return find(x) == find(y);
        }

        //联合x,y
        void unionElements(int x, int y) {

            //找出需要联合的两个节点的根节点
            int xRoot = find(x);
            int yRoot = find(y);

            //x , y 就是联合的
            if (xRoot == yRoot) {
                return;
            }

            //将x的根更新为y的根
            parent[xRoot] = yRoot;
        }


    };
}
#endif //UNIONFIND2_UNIONFIND2_H
